package graph;

/**
 * description:
 * author:张腾
 * date:2021-04-13
 */

/**
 * 检测一个图是否存在有向环
 * 使用一个onStack数组将正在搜索的节点设置为true来判断是否由节点在一次搜索中被走了两次
 */
public class DirectedCycle {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;

    //记录图中是否有环
    private boolean hasCycle;

    //记录当前顶点有没有已经处于正在搜索的有向路径中
    private boolean[] onStack;

    public DirectedCycle(DiGraph G){
        this.marked = new boolean[G.V()];
        this.hasCycle = false;
        this.onStack = new boolean[G.V()];

        //找到图中每一个顶点，让每一个顶点 如果还没有搜索过则作为入口，调用dfs进行搜索
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]){
                dfs(G,i);
            }
        }
    }

    //基于深度优先搜素，检测图G中是否有环
    private void dfs(DiGraph G,int v){
        //把顶点v设置为已搜索
        marked[v] = true;
        //当前节点入栈
        onStack[v] = true;

        for (Integer w : G.adj(v)) {
            //如果没有搜索过，则递归调用进行搜索
            if (!marked[w]){
                dfs(G,w);
            }

            //已经搜索过，再判断是否在栈中：正在搜索
            if (onStack[w]){
                hasCycle = true;
                return;
            }
        }

        onStack[v] = false;
    }

    //判断当前有向图是否有环
    public boolean hasCycle(){

        return false;
    }
}
